package tree.heapSort;
/**
 * 参考https://www.cnblogs.com/jingmoxukong/p/4303826.html
 */
public class HeapSort {
    public static void main(String[] args) {
        // 初始化一个序列
        int[] array = {
                1, 3, 4, 5, 2, 6, 9, 7, 8, 0
        };
        // 调用快速排序方法
        System.out.print("排序前:\t");
        printPart(array, 0, array.length - 1);
        heapSort(array);
        System.out.print("排序后:\t");
        printPart(array, 0, array.length - 1);
    }

    public static void adjustHeap(int[] arr, int parent, int length) {
        int temp = arr[parent]; // temp保存当前父节点
        int child = 2 * parent + 1;  // 获得左孩子
        while (child < length) {
            // 如果有右孩子 并且右孩子大于左孩子节点
            if (child + 1 < length && arr[child + 1] > arr[child]) {
                child++;
            }
            // 如果父结点的值已经大于孩子结点的值，则直接结束
            if (temp > arr[child]) {
                break;
            }
            // 把孩子结点的值赋给父结点
            arr[parent] = arr[child];

            // 选取孩子结点的左孩子结点,继续向下筛选
            parent = child;
            child = child * 2 + 1;
        }
        arr[parent] = temp;
    }
    public static void heapSort(int []arr){
        // 构建一个大顶堆
        for (int i = arr.length-1; i >=0 ; i--) {
            adjustHeap(arr,i,arr.length);
        }
        for (int i = arr.length-1; i >0; i--) {
            swap(arr,0,i);
            adjustHeap(arr,0,i);
            System.out.printf("第 %d趟:\t",arr.length-i);
            printPart(arr,0,arr.length-1);
        }
    }
    // 抽取交换方法
    public static void swap(int []arr,int a ,int b){
        int temp=arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
    // 打印序列
    public static void printPart(int[] list, int begin, int end) {
        for (int i = 0; i < begin; i++) {
            System.out.print("\t");
        }
        for (int i = begin; i <= end; i++) {
            System.out.print(list[i] + "\t");
        }
        System.out.println();
    }
}